package basicSort.quickSort;

import java.util.Arrays;

//基本快排  面对有序数组的时候效率极低.

public class QuickSort {

    public static int[] qsort(int[] arr){

        //空值判断
        if( arr == null || arr.length < 2 ){
            return arr;
        }

        psort( arr , 0 , arr.length - 1 );

        return arr;
    }

    public static void psort(int[] arr , int l , int r){
        if (l<r){
            int[] p = partion( arr , l , r);
            psort( arr , l ,p[0]);
            psort( arr , p[1] , r);
        }
    }

    public static int[] partion( int[] arr , int l , int r){

        int index = l-1;

        int flag = arr[r];

        while ( l < r ){
            if( arr[l] < flag){
                swap(arr,++index,l++);
            }else {
                l++;
            }
        }
        swap( arr , index+1 , r);
        return new int[]{index,index+2};
    }

    public static void swap(int[] arr , int i ,int j ){
        int temp = arr[i] ;
        arr[i] = arr[j] ;
        arr[j] = temp;
    }

    public static void main(String[] args) {


        int count = 100;

        int[] arr = new int[count];

        for ( int i = 0 ; i < count ; i++){
            arr[i] =(int) (Math.random() * 100);
        }

        System.out.println("arr:  ");

        for( int i = 0 ; i < arr.length ; i++){
            System.out.print(arr[i]+" ");
        }

        int[] arr2 = new int[count];

        System.arraycopy( arr , 0 , arr2 , 0 , count);

        System.out.println();
        System.out.println("arr2:  ");

        for( int i = 0 ; i < arr2.length ; i++){
            System.out.print(arr2[i] + " ");
        }

        System.out.println();

        //int[] arr = new int[]{3,8,6,2,7,9,1,4,5};
        qsort(arr);
        for( int i = 0 ; i < arr.length ; i++){
            System.out.print(arr[i]+" ");
        }

        System.out.println();

        Arrays.sort(arr2);
        for( int i = 0 ; i < arr2.length ; i++){
            System.out.print(arr2[i] + " ");
        }
    }

}
